#ifndef _TAVLCOM__H_
#define _TAVLCOM__H_

#include "tcomplejo.h"
#include "tlistacom.h"
#include <vector>

//! \file tavlcom.h
//! \brief Cabeceras de la clase TAVLCom y auxiliares

class TAVLNodo;

//! \class TAVLCom
/*!	\brief Clase que implementa un árbol AVL*/

class TAVLCom
{
	public:
		//! \brief Constructor por defecto de TAVLCom
		/*!	Construye un arbol AVL vacio*/
		TAVLCom():raiz(0){};
		//! \brief Constructor de copia de TAVLCom
		/*!	Construye un árbol AVL copia de otro*/
		TAVLCom(TAVLCom &);
		//! \brief Destructor de TAVLCom
		/*!	Libera la memoria ocupada del árbol AVL*/
		~TAVLCom();
		//! \brief Operador =
		/*!	Asigna un árbol AVL a otro*/
		TAVLCom & operator=(const TAVLCom &);
		//! \brief Operador ==
		/*!	Devuelve verdadero si ambos árboles son iguales*/
		bool operator==(const TAVLCom &) const;
		//! \brief Operador != 
		/*!	Devuelve verdadero si los árboles son distintos*/
		bool operator!=(const TAVLCom &) const;
		//! \brief EsVacio
		/*!	Devuelve true si el árbol AVL está vacio*/
		bool EsVacio() const;
		//! \brief Insertar
		/*!	Inserta un TComplejo en el árbol y devuelve true si lo consigue*/
		bool Insertar(const TComplejo &);
		//! \brief Buscar
		/*!	Devuelve true si el TComplejo ha sido previamente insertado*/
		bool Buscar(const TComplejo &) const;
		//! \brief Altura
		/*!	Devuelve la altura del árbol (camino crítico)*/
		int Altura() const;
		//! \brief Nodos
		/*!	Devuelve el número de nodos del árbol*/
		int Nodos() const;
		//! \brief NodosHoja
		/*!	Devuelve el número de nodos del árbol sin hijos*/
		int NodosHoja() const;
		//! \brief Inorden
		/*!	Devuelve el recorrido Inorden del árbol*/
		TListaCom Inorden() const;
		//! \brief Preorden
		/*!	Devuelve el recorrido Preorden del árbol*/
		TListaCom Preorden() const;
		//! \brief Postorden
		/*!	Devuelve el recorrido Postorden del árbol*/
		TListaCom Postorden() const;
		//! \brief Niveles
		/*!	Devuelve el recorrido por niveles del árbol*/
		TListaCom Niveles() const;
		//! \brief Borrar
		/*!	Borra un TComplejo y devuelve true si lo consigue*/
		bool Borrar(const TComplejo &);

	
	private:
		//! \brief TAVLNodo *raiz
		/*!	Raíz del arbol AVL*/
		TAVLNodo *raiz;
		
		//! \brief InordenAux
		/*!	Método privado que devuelve el recorrido Inorden en la lista pasada como argumento*/
		void InordenAux(TListaCom &) const;
		//! \brief PreordenAux
		/*!	Método privado que devuelve el recorrido Preorden en la lista pasada como argumento*/
		void PreordenAux(TListaCom &) const;
		//! \brief PostordenAux
		/*!	Método privado que devuelve el recorrido Postorden en la lista pasada como argumento*/
		void PostordenAux(TListaCom &) const;
		//! \brief Equilibrar
		/*!	Equilibra el árbol desde el que se llama. Se llama a la vuelta de la llamada recursiva
		 * al insertar y borrar*/
		void Equilibrar();
		//! \brief BuscarSustitutoMayor
		/*!	Devuelve el mayor de la izquierda de un árbol. Usado en Borrar*/
		TComplejo BuscarSustitutoMayor();
		//! \brief BuscarSustitutoMenor
		/*!	Devuelve el menor de la derecha de un árbol. Usado en Borrar*/
		TComplejo BuscarSustitutoMenor();

};

//! \class TAVLNodo
/*!	\brief Clase que implementa un nodo de un árbol AVL*/

class TAVLNodo
{
	friend class TAVLCom;
	public:
		//! \brief Constructor por defecto de TAVLNodo
		/*!	Construye un nodo de árbol AVL*/
		TAVLNodo(){};
		//! \brief Constructor de copia de TAVLNodo
		/*!	Construye un nodo de árbol AVL copia de otro*/
		TAVLNodo(const TAVLNodo &);
		//! \brief Destructor de TAVLNodo
		/*!	Libera la memoria de un nodo*/
		~TAVLNodo();
		//! \brief Operador = 
		/*!	Asigna TAVLNodo*/
		TAVLNodo & operator=(const TAVLNodo &);

	private:
		//! \brief TComplejo item
		/*!	Dato que almacena el nodo*/
		TComplejo item;
		//! \brief TAVLCom iz
		/*!	Hijo izquierdo del nodo*/
		TAVLCom iz;
		//! \brief TAVLCom de
		/*!	Hijo derecho del nodo*/
		TAVLCom de;
		//! \brief int fe
		/*!	Factor de equilibrio del nodo*/
		int fe;
};



class TAVLCNodo;

//! \class TAVLCola
/*!	\brief Clase que implementa una cola de punteros a TAVLNodo*/

class TAVLCola
{
	public:
		//! \brief Constructor por defecto de TAVLCola
		/*!	Crea una cola de punteros a TAVLNodo vacía*/
		TAVLCola():prim(NULL),ult(NULL){};
		//! \brief Constructor de copia de TAVLCola
		/*!	Crea una nueva cola de punteros a TAVLNodo copia de otra*/
		TAVLCola(const TAVLCola &);
		//! \brief Destructor de TAVLCola
		/*!	Libera la memoria de una cola*/
		~TAVLCola();
		//! \brief Encolar
		/*!	Añade un puntero a TAVLCom al final de la cola*/
		bool Encolar(TAVLCom*);
		//! \brief Cabeza
		/*!	Devuelve el primer elemento de la cola*/
		TAVLCom* Cabeza();
		//! \brief EsVacia
		/*!	Devuelve true si la cola es vacía*/
		bool EsVacia(){return !prim;};
		//! \brief Desencolar
		/*!	Borra el primer elemento de la cola*/
		bool Desencolar();
	
	
	private:
		//! \brief TAVLCNodo* prim
		/*!	Cabeza de la cola*/
		TAVLCNodo* prim;
		//! \brief TAVLCNodo* ult
		/*!	Final de la cola*/
		TAVLCNodo* ult;
};

//! \class TAVLCom
/*!	\brief Clase que implementa un nodo de cola de punteros a TAVLCom*/

class TAVLCNodo
{
	friend class TAVLCola;
	public:
		//! \brief Constructor por defecto de TAVLCNodo
		/*!	Crea un nodo de cola de punteros a TAVLCom vacío*/
		TAVLCNodo():a(NULL),sig(NULL){};
		//! \brief Constructor de copia TAVLCNodo
		/*!	Crea un nodo de cola de punteros a TAVLCom copia de otro*/
		TAVLCNodo(const TAVLCNodo&);
		//! \brief Destructor de TAVLCNodo
		/*! Libera la memoria de un nodo*/
		~TAVLCNodo();
	
	private: 
		//! \brief TAVLCom* a
		/*!	Puntero a árbol que almacenamos*/
		TAVLCom* a;
		//! \brief TAVLCNodo* sig
		/*!	Siguiente elemento de la cola*/
		TAVLCNodo* sig;

};
#endif
